package com.datastructures2.graph.有向图;

import edu.princeton.cs.algs4.TransitiveClosure;

/**
 * 计算强连通分量的Kosaraju算法
 * @author MaoLin Wang
 * @date 2020/2/2216:54
 */
public class KosarajuSCC {
    private boolean[] marked;
    /**
     * 强连通分量的标识符
     */
    private int[] id;
    /**
     * 强连通分量个数
     */
    private int count;

    public KosarajuSCC(Digraph digraph){
        marked=new boolean[digraph.V()];
        id=new int[digraph.V()];
        //求反向图的逆后序
        DepthFirstOrder order=new DepthFirstOrder(digraph.reverse());
        //对逆后序进行dfs遍历
        for(int s: order.reversePost()){
            if (!marked[s]){
                dfs(digraph,s);
                count++;
            }
        }
    }

    private void dfs(Digraph digraph, int v) {
        marked[v]=true;
        //顶点v属于第count个强连通分量
        id[v]=count;
        for (int w: digraph.adj(v)){
            if (!marked[w]){
                dfs(digraph,w);
            }


        }
    }
    /*v和w是否强连通*/
    public boolean stronglyConnected(int v,int w){
        return id[v]==id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return count;
    }
}
